// 134. 加油站
// 思路：定义三个变量，start、cur_gas、total_gas
// start记录开始的位置，cur_gas记录当前的油量，total_gas记录总的油量
// 当gas与cost的差值大于等于0的时候，start就从该位置开始走
// 此时开始，cur_gas就是累加，当累加值小于0时，意味着汽车到不了下一个位置，
// 此时start就要重新记录位置，且cur_gas赋为0从头开始
// 遍历完整个数组后，total_gas >= 0的话就说明从start位置开始走，是可以走一圈的


#include <vector>
using namespace std;

class Solution
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int start = 0, cur_gas = 0, total_gas = 0;
        for(int i = 0; i < gas.size(); i++)
        {
            cur_gas += (gas[i]-cost[i]);
            total_gas += (gas[i]-cost[i]);
            if(cur_gas < 0)//当前油量小于0，开始位置就要从下一个开始算
            {
                start = i + 1;
                cur_gas = 0;
            }
        }
        return total_gas >= 0 ? start : -1;
    }
};